package com.MSB2.sort1;

/**
 * 6  3  15  2  1  6  7
 * 2  1  4
 * 7
 * 右边的数乘2还小于这个数，这样的数有多少个
 * 每个数这样计算，求和
 */
public class BiggerRightTwice {
    public static void main(String[] args) {
        int[] arr = new int[]{6, 3, 15, 2, 1, 6, 7};
        int sum = pairSum(arr);
        System.out.println(sum);
    }

    public static int pairSum(int[] arr){
        if (arr == null || arr.length < 2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int process(int[] arr, int L, int R){
        if (L == R)
            return 0;
        int mid = L + ((R - L) >> 1);
        int num1 = process(arr, L, mid);
        int num2 = process(arr, mid + 1, R);
        int num3 = mergeCal(arr, L, mid, R);
        merge(arr, L, mid, R);
        return num1 + num2 + num3;
    }

    private static int mergeCal(int[] arr, int l, int mid, int r) {
        int sum = 0;
        int p2 = mid + 1;
        for (int i = l; i <= mid; i++) {
            while (p2 <= r && arr[i] > (arr[p2] << 1)){
                p2 ++;
            }
            sum += p2 - mid - 1;
        }
        return sum;
    }

    /**
     * 合并两个排好序的数组
     * @param arr 数组
     * @param l 左
     * @param mid 中
     * @param r 右
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        System.arraycopy(help, 0, arr, l, help.length);
    }
}
